//删除有序数组中的重复项 II
/*给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成
1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按升序排列
*/
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int left = -1, right = 0;
        int floag = 0;
        while (right < nums.size()) {
            if (left >= 0 && nums[right] == nums[left]) {
                floag++;
            }
            if (left == -1 || nums[left] != nums[right]) {
                left++;
                swap(nums[left], nums[right]);
                floag = 0;
            } else if (floag <= 1) {
                left++;
                swap(nums[left], nums[right]);
            }
            right++;
        }
        return left + 1;
        // return 0;
    }
};


//买卖股票的最佳时机 II
/*给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。
1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104
*/
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 1)
            return 0;
        int sum = 0;
        for (int i = 0; i < prices.size() - 1; i++) {
            if (prices[i] < prices[i + 1]) {
                sum += (prices[i+1] - prices[i]);
            }
        }
        return sum;
    }
};

//最小覆盖子串
/*给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
m == s.length
n == t.length
1 <= m, n <= 105
s 和 t 由英文字母组成
*/
class Solution {
public:
    string minWindow(string s, string t) {
        string S;
        int hash1[128] = {0};
        int hash2[128] = {0};
        int t_sum = 0;
        int ret = s.size()+1;
        int index = -1;
        for (auto& c : t) {
            hash2[c]++;
            t_sum++;
        }
        int left = 0, right = 0, count = 0;
        while (right < s.size()) {
            hash1[s[right]]++;
            if (hash1[s[right]] <= hash2[s[right]])
                count++;
            // cout<<count<<" ";
            while (count == t_sum) {
                if (ret > right - left + 1) {
                    ret = right - left + 1;
                    index = left;
                }
                if (hash1[s[left]] <= hash2[s[left]])
                    count--;
                hash1[s[left]]--;
                left++;
            }
            right++;
        }
        if (index == -1)
            return "";
        S = s.substr(index, ret);
        return S;
    }
};


//K 个一组翻转链表
/*给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reverselist(ListNode* head, ListNode* end) {
        ListNode* n1 = end;
        ListNode* n2 = head;
        ListNode* n3 = head->next;
        while (n2 != end) {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if (n3 != end)
                n3 = n3->next;
        }
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        int quick = 1;
        int floag = 0;
        ListNode *_slow = new ListNode(-1, head), *_quick = head;
        while (_quick) {
            if (quick % k == 0) {
                if (floag == 0) {
                    head = _quick;
                    floag = 1;
                }
                reverselist(_slow->next, _quick->next);
                ListNode* temp = _slow->next;
                _slow->next = _quick;
                _slow = temp;
                _quick = temp;
            }
            quick++;
            _quick = _quick->next;
        }
        return head;
    }
};